package com.ljc;

import com.ljc.dto.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author clj
 * @date 2023/2/10
 * @desc
 * Given the root of a binary tree, return the preorder traversal of its nodes' values.
 */
public class E145BinaryTreePostorderTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        root.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        System.out.println(preOrderTraversal(root));


    }

    public static List<Integer> postOrderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postOrder1(root, res);
        return res;
    }

    public static void postOrder1(TreeNode root, List<Integer> res) {
        if(root == null) {
            return;
        }
        postOrder1(root.left, res);
        postOrder1(root.right, res);
        res.add(root.val);
    }

    public static List<Integer> preOrderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preOrder(root, res);
        return res;
    }

    /**
     * 前序遍历，先访问根节点，再遍历左节点，最后遍历右节点。
     * @param root
     * @param res
     */
    public static void preOrder(TreeNode root, List<Integer> res) {
        if(root == null) {
            return;
        }
        res.add(root.val);
        preOrder(root.left, res);
        preOrder(root.right, res);
    }

    /**
     * 二叉树的后序遍历，先遍历左节点，再遍历右节点，最后访问根节点。
     */
    public static List<Integer> postOrderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postOrder(root, res);
        return res;
    }

    /**
     * postOrder(root.left, res);实现
     */
    public static void postOrder(TreeNode root, List<Integer> res) {
        if(root == null) {
            return;
        }
        postOrder(root.left, res);
        postOrder(root.right, res);
        res.add(root.val);
    }
}
